// 数据流的中位数：https://leetcode-cn.com/problems/find-median-from-data-stream/
/*
        维护两个堆， 一个大根堆，一个小根堆
        1. 大根堆记录前半段数据的最大值， 小根堆记录后半段数据的最小值
        2. 奇数时，大根堆数据比小根堆多一个， 返回大根堆堆顶， 偶数时，取各自堆顶求平均值
        3. 维系关系： 
            （1）大根堆元素个数一定大于等于小根堆个数，且不超过1
            （2）大根堆堆顶元素一定是小于 小根堆堆顶元素
        举例子：
            2345  689  分别是大根堆小根堆元素
*/


// 大顶堆 + 小顶堆
class MedianFinder{

    // 大顶堆用于存储较小的一半元素
    private PriorityQueue<Integer> maxHeap;
    // 小顶堆用于存储较大的一半元素
    private PriorityQueue<Integer> minHeap;

    // 注意：如果元素的个数是奇数的话，那么大顶堆中的元素个数比小顶堆中元素个数多 1

    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
    
    // 时间复杂度：O(logn)
    public void addNum(int num) {
        if (maxHeap.isEmpty()) {
            maxHeap.add(num);
            return;
        }

        if (num <= maxHeap.peek()) { 
            // 到这里，说明 num 属于较小的元素，所以存储在大顶堆
            maxHeap.add(num);
        } else {
            // 到这里，num 属于较大的元素
            minHeap.add(num);
        }

        // 维护好两个堆中的元素个数，原则：
        // 1. 如果是有偶数个元素的话，那么大顶堆和小顶堆是相同的
        // 2. 如果是有奇数个元素的话，那么大顶堆元素的个数比小顶堆多 1 个
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.add(maxHeap.remove());
        }

        if (maxHeap.size() < minHeap.size()) {
            maxHeap.add(minHeap.remove());
        }
    }
    
    // 时间复杂度：O(1)
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            // 说明有奇数个元素，那么大顶堆堆顶元素就是中位数
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) * 0.5;
        }
    }
}